/*!
 * \file Proyectable.cpp
 *
 * \date Jan 28, 2014
 * \author correa
 */

#include <cstring>
#include <Proyectable.h>

using namespace std;

//constructor
Proyectable::Proyectable(int n) : Grafo(n)
{
	initialize();
}

//constructor
Proyectable::Proyectable(Proyectable& otro) : Grafo(otro)
{
	_vecindadComun = new VertexSet(getN());
	_vecindadComun->copyAll(*(otro._vecindadComun));

	_vecinosUnidos = new VertexSet(getN());
	_vecinosUnidos->copyAll(*(otro._vecinosUnidos));

	_noVecinos= new VertexSet(getN());
	_noVecinos->copyAll(*(otro._noVecinos));

	_subgrafo = new VertexSet(getN());
	_subgrafo->copyAll(*otro._subgrafo);

	_subnode = new SingleNodeSet();
	_subnode->copyAll(*otro._subnode);

	_falsonode = new SingleNodeSet();
	_falsonode->copyAll(*otro._falsonode);

	_complQ = new VertexSet(getN());
	_complQ->copyAll(*otro._complQ);

	_enumerablesII = new Lista(getN());
	(*_enumerablesII) = (*otro._enumerablesII);
}

//constructor
Proyectable::Proyectable(Grafo& otro) : Grafo(otro)
{
	initialize();
}

//constructor
Proyectable::Proyectable(string archivoDIMACS) : Grafo(archivoDIMACS)
{
	initialize();
}

void Proyectable::initialize()
{
	_vecindadComun = new VertexSet(getN());
	_vecinosUnidos = new VertexSet(getN());
	_noVecinos = new VertexSet(getN());
	_subgrafo = new VertexSet(getN());
	_complQ = new VertexSet(getN());
	_subnode = new SingleNodeSet();
	_falsonode = new SingleNodeSet();
	_enumerablesII = new Lista(getN());
}

//destructor
Proyectable::~Proyectable()
{
	delete _vecindadComun;
	delete _vecinosUnidos;
	delete _noVecinos;
	delete _enumerablesII;
	delete _subgrafo;
	delete _complQ;
	delete _subnode;
	delete _falsonode;
}

void Proyectable::copy(Grafo& otro)
{
	_vecindadComun->removeAll();
	_vecinosUnidos->removeAll();
	Grafo::copy(otro);
}

void Proyectable::copySubgrafo(const Grafo& otro, const VertexSet& subgrafo)
{
	_vecindadComun->removeAll();
	_vecinosUnidos->removeAll();
	Grafo::copySubgrafo(otro, subgrafo);
}

void Proyectable::relajarClique(VertexSet &clique, const int u, Grafo &falso)
{
	_subgrafo->copyAll(vecinos(u));
	_subgrafo->removeAll(clique);
	_complQ->copyAll(*_subgrafo);

	int nodeidx = 0;
	int lastnode = NODEIDX(_n-1);

	while (nodeidx <= lastnode) {
		_subgrafo->nodeView(nodeidx, *_subnode);
		int vidx = _subnode->least();
		while (vidx >= 0) {
			int v = NELEM(nodeidx)+vidx;
			_complQ->remove(v);
			_subgrafo->retainAll(vecinos(v));
			vidx = _subnode->least();
		}
		nodeidx++;
	}

	_enumerablesI->clear();
	_complQ->lista(*_enumerablesI);
	if (_enumerablesI->cantidad() > 0)
	{
		falso.addVertice(u);
		for (int i = 0; i < _enumerablesI->cantidad(); i++)
		{
			int ei = (*_enumerablesI)[i];
			delArista(u, ei);
			falso.addVertice(ei);
			falso.addArista(u, ei);
		}
	}

}

void Proyectable::restituir(Grafo* falsog)
{
	_enumerablesI->clear();
	falsog->vertices().lista(*_enumerablesI);
	for (int i=0; i < _enumerablesI->cantidad(); i++)
	{
		int ei = (*_enumerablesI)[i];
		_arista[ei]->addAll(falsog->vecinos(ei));
	}
}

/*!
 * \brief Clique projection
 *
 * \return \c true, si agrega aristas falsas; \c false, sino
 */
bool Proyectable::proyectarCliqueFuerte(ProjectableCliqueSet &clique, const VertexSet &subgrafo, Grafo &falso)
{
	Lista& lc = clique.lista();
	int u = lc[0];
	for (int i = 1; i < lc.cantidad(); i++)
		if (vecinos(lc[i]).size() < vecinos(u).size())
			u = lc[i];
	relajarClique(clique, u, falso);

	if (proyectarClique(clique, subgrafo, falso))
	{
		clique.addVecindadComun(*_vecindadComun);
		return true;
	}

	return false;
}

/*!
 * \brief Clique projection
 *
 * \return \c true, si agrega aristas falsas; \c false, sino
 */
bool Proyectable::proyectarClique(ProjectableCliqueSet &clique, const VertexSet &subgrafo, Grafo &falso)
{
	Lista& lc = clique.lista();
	actualizarVecindades(subgrafo, clique);

	int u = 0, v = 0;
	bool isEdge = (lc.cantidad() == 2);
	if ( isEdge )
	{
		u = lc[0];
		v = lc[1];
	}

	_vecinosUnidos->removeAll(clique);
	_vecinosUnidos->removeAll(*_vecindadComun);

	_enumerablesI->clear();
	_vecinosUnidos->lista(*_enumerablesI);

	bool ret = false;
	for(int i=0; i<_enumerablesI->cantidad(); ++i)
	{
		int ei = (*_enumerablesI)[i];
		_noVecinos->copyAll(*_vecinosUnidos);
		_noVecinos->removeAll(vecinos(ei));
		_noVecinos->remove(ei);

		_enumerablesII->clear();
		_noVecinos->lista(*_enumerablesII);

		for(int j=0; j<_enumerablesII->cantidad(); ++j)
		{
			int ej = (*_enumerablesII)[j];

			if ( isEdge )
			{
				if( (isArista(ei,u) && isArista(ej,v)) || (isArista(ej,u) && isArista(ei,v)))
				{
					ret = true;
					addArista(ei, ej);
					falso.addVertice(ei);
					falso.addVertice(ej);
					falso.addArista(ei, ej);
				}

			}
			else
			{
				VertexSet unionVecinos(getN());
				unionVecinos.copyAll(vecinos(ei));
				unionVecinos.addAll(vecinos(ej));

				if( clique.isSubsetOf(unionVecinos) )
				{
					ret = true;
					addArista(ei, ej);
					falso.addVertice(ei);
					falso.addVertice(ej);
					falso.addArista(ei, ej);
				}
			}
		}
	}

	return ret;
}

/*!
 * \brief Calcula la vecindad comun a la clique
 *
 * \c _enumerables debe contener los elementos cuyas vecindades son actualizadas
 */
void Proyectable::actualizarVecindades(const VertexSet &subgrafo, ProjectableCliqueSet& clique)
{
	_vecindadComun->copyAll(subgrafo);
	_vecinosUnidos->removeAll();

	Lista& lc = clique.lista();
	for(int i=0; i<lc.cantidad(); ++i)
	{
		int e = lc[i];
		_vecindadComun->retainAll(vecinos(e));
		_vecinosUnidos->addAll(vecinos(e));
	}

	_vecinosUnidos->retainAll(subgrafo);
}

/*!
 * \brief Borra aristas falsas
 *
 */
void Proyectable::borrar(Grafo* falsog)
{
	_enumerablesI->clear();
	falsog->vertices().lista(*_enumerablesI);
	for (int i=0; i < _enumerablesI->cantidad(); i++)
	{
		int ei = (*_enumerablesI)[i];
		_subgrafo->copyAll(falsog->vecinos(ei));
		((VertexSet&) falsog->vecinos(ei)).removeAll(*_arista[ei]);
		_arista[ei]->removeAll(*_subgrafo);
	}
}
